public class Main {
    class ListNode{
        int val;
        ListNode next;
        public ListNode(int val) {
            this.val = val;
        }
    }
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if(head == null){
            return null;
        }
        ListNode dummyNode = new ListNode(-1);
        dummyNode.next = head;
        int length = 0;
        ListNode curr = dummyNode;
        // 1.计算链表长度
        while(curr != null){
            length++;
            curr = curr.next;
        }
        // 2.找到前驱节点
        ListNode prev = dummyNode;
        for(int i = 1; i < length-n ; i++){
            prev = prev.next;
        }
        ListNode delNode = prev.next;
        prev.next = delNode.next;
        delNode.next = null;
        return dummyNode.next;
    }

    public ListNode middleNode(ListNode head) {
        if(head == null){
            return null;
        }
        if(head.next == null){
            return head;
        }
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }

    public ListNode insertionSortList(ListNode head) {
        if(head == null ||head.next == null) return head;
        ListNode dummyNode = new ListNode(-1);
        dummyNode.next = head;
        ListNode prev = head;
        ListNode cur = head.next;
        while(cur != null){
            if(prev.val > cur.val){
                ListNode p = dummyNode;
                while(p.next.val <= cur.val){
                    p = p.next;
                }
                prev.next = cur.next;
                cur.next = p.next;
                p.next = cur;
            }
            prev = cur;
            cur = cur.next;
        }
        return dummyNode.next;
    }

    public ListNode mergeKLists(ListNode[] lists) {
        if(lists == null ||lists.length == 0) return null;
        return merge(lists,0,lists.length-1);
    }

    public ListNode merge(ListNode[] lists,int left,int right){
        if(left == right) return lists[left];
        if(left > right) return null;

        int mid = left+(right-left)/2;
        ListNode leftMerge = merge(lists,left,mid);
        ListNode rightMerge = merge(lists,mid+1,right);

        return mergeTwoLists(leftMerge,rightMerge);
    }

    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if (list1 == null)
            return list2;
        if (list2 == null)
            return list1;
        ListNode dummyNode = new ListNode(-1);
        ListNode cur = dummyNode;

        while (list1 != null && list2 != null) {
            if (list1.val <= list2.val) {
                cur.next = list1;
                list1 = list1.next;
            } else {
                cur.next = list2;
                list2 = list2.next;
            }
            cur = cur.next;
        }

        if (list1 == null) {
            cur.next = list2;
        }

        if (list2 == null) {
            cur.next = list1;
        }
        return dummyNode.next;
    }


    public static void main(String[] args) {
        System.out.println("Hello world!");
    }
}